package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/26 13:21
 * 买卖股票的最佳时机 II
 * 尽可能得多赚钱(可以多次交易)
 */
public class maxProfit2 {
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit1(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit3(new int[]{7, 1, 5, 3, 6, 4}));
    }

    // dp 状态定义: dp[i][0] 表示手上没有股票时的最大收益，dp[i][1] 表示手上持有股票时的最大收益
    // dp 初始值：dp[0][0] = 0, dp[0][1] = -prices[0]
    // dp 转移方程：
    //      dp[i][0] = Math.max(dp[i-1][0], prices[i] + dp[i-1][1]);
    //      dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public static int maxProfit1(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }

    // 空间复杂度优化：从 maxProfit1 可得知 dp[i][0], dp[i][1] 只与 dp[i-1][0], dp[i-1][1] 有关
    // 时间复杂度：O(n)，空间复杂度：O(1)
    public static int maxProfit2(int[] prices) {
        int dp0 = 0;
        int dp1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int temp0 = dp0;
            int temp1 = dp1;
            dp0 = Math.max(temp0, temp1 + prices[i]);
            dp1 = Math.max(temp1, temp0 - prices[i]);
        }
        return dp0;
    }

    // 贪心算法(推荐)：假定买了昨天的股票，如果今天的股票价格大于昨天的价格就有钱赚，简称有钱就赚 [1, 2, 3]
    // 题目可以转换成在一个 无序数组中 找到所有的单调递增阶段，然后把 递增阶段的首尾差值 累加
    // 时间复杂度：O(n)，空间复杂度：O(1)
    public static int maxProfit3(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max += Math.max(0, prices[i] - prices[i - 1]);
        }
        return max;
    }

    // dp 状态定义：dp[i] 表示 prices[i] 能获得的最大利润
    // dp 初始值：dp[0] = 0
    // dp 转移方程：dp[i] = Math.max(dp[i], (dp[j] + prices[i] - prices[j]));
    // 时间复杂度：O(n^2)，空间复杂度：O(n)
    // 作废：时间复杂度高，且没有技巧性和普遍性
    @Deprecated
    public static int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < i; j++) {
                // prices[i] > prices[j] 表示 j 买入，i 卖出 才有得赚
                if (prices[i] > prices[j]) {
                    dp[i] = Math.max(dp[i], (dp[j] + prices[i] - prices[j]));
                } else {
                    dp[i] = Math.max(dp[j], dp[i]);
                }
            }
            maxProfit = Math.max(dp[i], maxProfit);
        }
        return maxProfit;
    }
}
